package binary_tree.leetcode.medium;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author bruin_du
 * @description 二叉搜索树的后序遍历序列
 * @date 2022/6/5 14:52
 **/
public class Offer33_VerifyPostorder {
    public boolean verifyPostorder(int[] postorder) {
        //方法一：递归
//        if(postorder.length <= 1) return true;
//        return recursion(postorder, 0,postorder.length - 1);

        //方法二:单调栈
        if(postorder.length <= 1) return true;
        return method2(postorder);
    }

    private boolean method2(int[] postorder) {
        //root保存的是根结点的值,初始为无穷大
        int root = Integer.MAX_VALUE;
        Deque<Integer> deque = new ArrayDeque<>();
        //将搜索二叉树逆置为:根,右,左
        for (int i = postorder.length - 1; i >= 0; i--) {
            //如果左子树大于根结点,不满足二叉搜索树,返回false
            if(postorder[i] > root) return false;
            //循环将右树结点全部取出,root保存的就是当前的根结点
            while(!deque.isEmpty() && deque.peekLast() > postorder[i]){
                root = deque.pollLast();
            }
            //将结点存入
            deque.offerLast(postorder[i]);
        }
        return true;
    }

    private boolean recursion(int[] arr, int left, int right) {
        if(left >= right) return true;
        int root = arr[right--];
        int mid = left - 1;
        //如果有，找到第一个小于根的结点下标
        for (int i = right; i >= left; i--) {
            if(arr[i] < root) {
                mid = i;
                break;
            }
        }
        //在小于根结点的区间中有大于根结点的值.不满足搜索二叉树,返回false
        for (int i = left; i < mid; i++) {
            if(arr[i] > root) return false;
        }
        //根结点两边都满足时才为true
        boolean l = recursion(arr, left, mid - 1);
        boolean r = recursion(arr, mid + 1, right);
        return r && l;
    }
}
